МЕТОД СИНТЕЗА НЕИЗБЫТОЧНЫХ СХЕМ, ДОПУСКАЮЩИХ КОРОТКИЕ ЕДИНИЧНЫЕ ДИАГНОСТИЧЕСКИЕ ТЕСТЫ ПРИ КОНСТАНТНЫХ НЕИСПРАВНОСТЯХ НА ВЫХОДАХ ЭЛЕМЕНТОВ

Романов Дмитрий Сергеевич, кандидат физико-математических наук, доцент, кафедра математической кибернетики, Московский государственный университет имени М. В. Ломоносова (Россия, г. Москва, Ленинские горы, 1), romanov@cs.msu.ru
Романова Елена Юрьевна, кандидат педагогических наук, доцент, кафедра прикладной математики, Российский государственный социальный университет (Россия, г. Москва, ул. Вильгельма Пика, 4, стр. 1), klenar2001@mail.ru

519.718

DOI 

10.21685/2072-3040-2016-2-8

Актуальность и цели. Тестирование схем из функциональных элементов – это важная теоретическая задача, имеющая практические приложения к тестированию и верификации СБИС. Целью данной работы является демонстрация возможности построения для произвольной булевой функции схемы из функциональных элементов, реализующей эту функцию и допускающей короткий единичный диагностический тест при произвольных константных неисправностях на выходах элементов.
Материалы и методы. При получении основных результатов использовались методы синтеза схем, основанных на разложении булевой функции в полином Жегалкина.
Результаты. В статье устанавливается, что для произвольной булевой функции f, зависящей от n переменных, существует неизбыточная реализующая функцию f схема из функциональных элементов в базисе {x&y, x+y, 1}, допускающая единичный диагностический тест константной длины при произвольных константных неисправностях на выходах элементов.

схема из функциональных элементов, диагностический тест, произвольная константная неисправность на выходе элемента, функция Шеннона, легко-тестируемая схема.

1. Яблонский, С. В. О тестах для электрических схем / С. В. Яблонский, И. А. Чегис // Успехи математических наук. – 1955. – Т. 10, вып. 4 (66). – С. 182–184.
2. Чегис, И. А. Логические способы контроля электрических схем / И. А. Чегис, С. В. Яблонский // Труды МИАН СССР. – 1958. – Т. 51. – С. 270–360.
3. Редькин, Н. П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов / Н. П. Редькин // Вестник Московского университета. Серия 1. Математика. Механика. – 1992. – № 5. – С. 43–46.
4. Редькин, Н. П. О синтезе легкотестируемых схем в одном бесконечном базисе / Н. П. Редькин // Вестник Московского университета. Серия 1. Математика. Механика. – 2007. – № 3. – С. 29–33.
5. Коваценко, С. В. Синтез легкотестируемых схем в базисе Жегалкина для инверсных неисправностей / С. В. Коваценко // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. – 2000. – № 2. – С. 45–47.
6. Романов, Д. С. Метод синтеза легкотестируемых схем, допускающих единич-ные проверяющие тесты константной длины / Д. С. Романов // Дискретная математика.–2014.–Т.26,вып.2.–С.100–130.
7. Попков, К. А. О точном значении длины минимального единичного диагно-стического теста для одного класса схем / К. А. Попков. – М. : Изд-во ИПМ им. М. В. Келдыша РАН, 2015. – 20 с.
8. Романов, Д. С. Метод синтеза неизбыточных схем в базисе Жегалкина, допус-кающих единичные диагностические тесты длины один / Д. С. Романов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. – 2015. – № 4 (36). – С. 38–54.
9. Попков, К. А. О единичных диагностических тестах для схем из фугкциональ-ных элементов в базисе Жегалкина / К. А. Попков. – М. : Изд-во ИПМ им. М. В. Келдыша РАН, 2016. – 16 с.
10. Алехина, М. А. О надежности схем в базисах , при однотипных константных неисправностях на входах элементов / М. А. Алехина // Дискретный анализ и исследование операций. Серия 1. – 2001. – Т. 8, № 2. – С. 3–14.
11. Алехина, М. А. Нижние оценки ненадежности схем в некоторых базисах при однотипных константных неисправностях на входах элементов / М. А. Алехина // Дискретный анализ и исследование операций. Серия 1. – 2002. –Т. 9, № 3. – С. 3–28.
12. Алехина, М. А. Синтез и сложность надежных схем в базисе при од-нотипных константных неисправностях на входах элементов / М. А. Алехина // Дискретная математика. – 2003. – Т. 15, вып. 1. – С. 98–109.
13. Алехина, М. А. О сложности надежных схем из ненадежных элементов при однотипных константных неисправностях / М. А. Алехина // Дискретный анализ и исследование операций. Серия 1. – 2004. – Т. 11, № 2. – С. 3–17.
14. Алехина, М. А. О надежности схем в произвольном полном конечном базисе при однотипных константных неисправностях на выходах элементов / М. А. Але-хина // Дискретная математика. – 2012. – Т. 24, вып. 3. – С. 17–24.
15. Алехина, М. А. О надежности схем в базисе «антиконъюнкция» при констант-ных неисправностях на входах элементов / М. А. Алехина, В. В. Курышева // Известия вузов.Математика.–2016.–№7.–С.3–9.
16. Носков, В. Н. О длинах минимальных единичных диагностических тестов, контролирующих работу входов логических схем / В. Н. Носков // Методы дис-кретного анализа в синтезе управляющих систем. – 1978. – № 32. – С. 40–51.